import { checkArr } from "./util"

/**
 * 计数排序
 * @param arr 
 */
export const countSort = (arr: number[]) => {
    // 检查数组
    if (checkArr(arr)) return;



    const len = arr.length;
    // debugger

    // 1. 求出数组的最大和最小值
    let max = arr[0],
        min = arr[0];

    for (let i = 1; i < len; i++) {
        // 大于max, 更改max
        if (arr[i] > max) max = arr[i]

        // 小于min, 更改min
        if (arr[i] < min) min = arr[i]; 
    }   

    // 2. 创建max - min + 1大小的数组
    const newArr = new Array(max - min + 1).fill(0)
    
    // 3. 数组的每一项进行计数
    for (let i = 0; i < len; i++) {
        // 对相应的项执行++ (减去min是为了支持负数的情况)
        newArr[arr[i] - min]++
    }
    
    const arrLen = newArr.length;
    // debugger

    // 4. 每一项的计数加上前面的
    for (let i = 1; i < arrLen; i++) {
        newArr[i] += newArr[i - 1] 
    }

    // debugger
    // 5. 从后往前
    // 构建新的数组
    const newA = new Array(len);

    // newArr的下标就是arr[i] - min, 值代表加上自己一共右多少元素要排序 (--值代表自己所在的位置)
    for (let i = len; i >= 0; i--) {
        newA[--newArr[arr[i] - min]] = arr[i]
    }

    // 6. 覆盖arr
    for (let i = 0; i < len; i ++) {
        arr[i] = newA[i]
    }

}   